package leetcode.code0745;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

public class WordFilter {

	private Node root1;
	private Node root2;

	public WordFilter(String[] words) {
		root1 = new Node();
		root2 = new Node();
		for (int i = 0; i < words.length; i++) {
			char[] word = words[i].toCharArray();
			this.insert1(root1, word, i);
			this.insert2(root2, word, i);
		}
	}

	public int f(String pref, String suff) {
		List<Integer> ids1 = this.startsWith1(root1, pref);
		List<Integer> ids2 = this.startsWith2(root2, suff);
		if (ids1 == null || ids2 == null) {
			return -1;
		}
		int len1 = ids1.size();
		int len2 = ids2.size();
		int p1 = len1 - 1, p2 = len2 - 1;
		while (p1 >= 0 && p2 >= 0) {
			int id1 = ids1.get(p1);
			int id2 = ids2.get(p2);
			if (id1 == id2) {
				return id1;
			}
			if (id1 > id2) {
				p1--;
			} else {
				p2--;
			}
		}
		return -1;
	}

	private class Node {
		Node[] c = new Node[26];
		List<Integer> ids = new ArrayList<>();
	}

	public void insert1(Node root, char[] cs, int id) {
		Node node = root;
		for (int i = 0; i < cs.length; i++) {
			node = this.insert(node, cs, i, id);
		}
	}

	public void insert2(Node root, char[] cs, int id) {
		Node node = root;
		for (int i = cs.length - 1; i >= 0; i--) {
			node = this.insert(node, cs, i, id);
		}
	}

	public Node insert(Node node, char[] cs, int i, int id) {
		int idx = cs[i] - 'a';
		if (node.c[idx] == null)
			node.c[idx] = new Node();
		node = node.c[idx];
		node.ids.add(id);
		return node;
	}

	public List<Integer> startsWith1(Node root, String prefix) {
		Node node = root;
		char[] cs = prefix.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			if (node == null) {
				return null;
			}
			node = this.startsWith(node, cs, i);
		}
		return node == null ? null : node.ids;
	}

	public List<Integer> startsWith2(Node root, String suffix) {
		Node node = root;
		char[] cs = suffix.toCharArray();
		for (int i = cs.length - 1; i >= 0; i--) {
			if (node == null) {
				return null;
			}
			node = this.startsWith(node, cs, i);
		}
		return node == null ? null : node.ids;
	}

	public Node startsWith(Node node, char[] cs, int i) {
		int idx = cs[i] - 'a';
		if (node.c[idx] == null) {
			return null;
		}
		node = node.c[idx];
		return node;
	}

	public static void main(String[] args) {
		WordFilter wordFilter = new WordFilter(H.str2array2("[\"apple\"]"));
		int ans = wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀
		System.out.println(ans);
	}

}
